!not solved
package com.xinpan.exercise;

import java.util.ArrayList;

public class BestBuySell3 {
	   public int maxProfit(int[] prices) {
	        // Start typing your Java solution below
	        // DO NOT write main() function
	        if(prices.length < 2)
	            return 0;
	            
	        ArrayList<Integer> tmpList = new ArrayList<Integer>();
	        for(int i = 0; i < prices.length - 1; i++)
	            tmpList.add(prices[i+1] - prices[i]);
	       
	        
	        int hold = 0;
	        ArrayList<Integer> diffList = new ArrayList<Integer>();
	        for(Integer diff : tmpList)
	        {
	            if(diff < 0)
	            {
	                if(hold > 0)
	                {
	                    diffList.add(hold);
	                    hold = 0;
	                }
	                diffList.add(diff);
	            }
	            else
	            	hold += diff;
	        }
	        if(tmpList.get(tmpList.size() - 1) >=0)
	            diffList.add(hold);
	        
	     
	        int max = findSub(0, diffList.size() - 1, diffList);

	        return max;
	    }
	    
	   	public int findSub(int s, int e, ArrayList<Integer> list)
	   	{
	   		if(e - s == 0)
	   		{
	   			if(list.get(s) < 0)
	   				return 0;
	   			else
	   				return list.get(s);
	   		}
	   		
	   		int mid = (s + e) / 2;
	   		int max1 = findSub(s, mid, list);
	   		int max2 = findSub(mid+1, e, list);
	   		int max3 = findCross(s, e, mid, list);
	   		
	   		int max = max1;
	   		if(max2 > max)
	   			max = max2;
	   		if(max3 > max)
	   			max = max3;
	   		
	   		return max;
	   	}
	   	
	   	public int findCross(int s, int e, int mid, ArrayList<Integer> list)
	   	{
	 
	   		int sum = 0;
	   		int preMax = Integer.MIN_VALUE;
	   		for(int hold = mid; hold >= s; hold--)
	   		{
	   			sum += list.get(hold);
	   			if(sum > preMax)
	   				preMax = sum;
	   		}
	   		
	   		sum = 0;
	   		int nextMax = Integer.MIN_VALUE;
	   		for(int hold = mid + 1; hold <= e; hold++)
	   		{
	   			sum += list.get(hold);
	   			if(sum > nextMax)
	   				nextMax = sum;
	   		}
	   		
	   		sum = preMax + nextMax;
	   		if(sum > 0)
	   			return sum;
	   		return 0;
	   	}
	   	
	   	
	    public int maxSubProfit(int s, int e, ArrayList<Integer> diffList)
	    {
	        if(e - s < 0)
	            return 0;
	        
	        int max = 0;    
	        for(int sum = 0; s <= e; s++)
	        {
	            int diff = diffList.get(s);
	            
	            if(diff + sum < 0)
	            {
	                sum = 0;
	                continue;
	            }
	            sum += diff;
	            if(sum > max)
	                max = sum;
	        }
	        return max;
	    }
    
    public static void main(String[] args)
    {
    	BestBuySell3 bbs3 = new BestBuySell3();
    	int[] prices = {2,1,2,0,1};
    	System.out.println(bbs3.maxProfit(prices));
    }
}
